剑指offer 33.丑数

题目

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

思路

这里采用的是三指针法，任意丑数都是比这个数小的丑数乘以2，3，5其中之一得到的，要求按照顺序排列，那么就从之前的数中找到未被使用过的数乘一下，然后比较，就可以得到新的数了。
首先初始位为1，设三个指针值n2,n3,n5,初始设为0.之后开始循环，每次循环都找到235未乘过的数字乘一下，然后取最小值为新的丑数。之后，若n2n3n5使用过了，那么指针位+1，下次乘下一个数字，如果都可以，那就都加。把数字记录下来最后输出即可。

代码

public int GetUglyNumber_Solution(int index) {
  if(index==0){
    return 0;
  }
  int[] ans = new int[index];
  int n2 = 0, n3 = 0, n5 = 0;
  ans[0] = 1;
  for (int i = 1; i < index; i++) {
    int min = Math.min(ans[n2] * 2, Math.min(ans[n3] * 3, ans[n5] * 5));
    ans[i] = min;
    if (min == ans[n2]*2) {
      n2++;
    }
    if (min == ans[n3]*3) {
      n3++;
    }
    if (min == ans[n5]*5) {
      n5++;
    }

  }
  return ans[index-1];
}